/*
 ============================================================================
 Name        : searchtree.c
 Author      : Jfhu
 Version     :
 Copyright   : Your copyright notice
 Description : Hello World in C, Ansi-style
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include "searchtree.h"

void initializenode(pNode n)
{
	n->leftChild = n->rightChild = n->parent = NULL;
}

void initializenode1(pNode n, int key)
{
	n->key = key;
	n->leftChild = n->rightChild = n->parent = NULL;
}

pNode access(int key, searchtree s)
{
	if (s == NULL)
		return NULL;

	return visit(key, *s);
}

pNode visit(int key, pNode n)
{
	if (n == NULL)
		return NULL;

	if (key < n->key)
		return visit(key, n->leftChild);

	if (key > n->key)
		return visit(key, n->rightChild);

	return n;
}

void insert(pNode n, searchtree s)
{
	if ((*s) == NULL) {
		(*s) = n;
		return;
	}

	insertNode(n, *s);
}

void insertNode(pNode n, pNode s)
{

	if (n->key < s->key) {
		if (s->leftChild == NULL) {
			s->leftChild = n;
			n->parent = s;
		} else {
			insertNode(n, s->leftChild);
		}
	}  else if (n->key > s->key){
		if (s->rightChild == NULL) {
			s->rightChild = n;
			n->parent = s;
		} else {
			insertNode(n, s->rightChild);
		}
	 }
}

void delete(pNode n, searchtree s)
{
	if (s == NULL || (*s) == NULL)
		return;

	deleteNode(n, *s);
}


void deleteNode(pNode n, pNode s)
{
	pNode p = NULL;
	if (n == NULL)
		return;

	p = n->parent;

	while (n->leftChild != NULL && n->leftChild->rightChild != NULL) {
		n->key = n->leftChild->rightChild->key;
		p = n->leftChild;
		n = n->leftChild->rightChild;
	}

	if (n->leftChild == NULL) {
		if (n->rightChild == NULL) {
			n = NULL;
		} else {
			n->rightChild->parent = p;
			if (n->key > p->key) {
				p->rightChild = n->rightChild;
			} else {
				p->leftChild = n->rightChild;
			}
		}
	} else {
		n->leftChild->parent = p;
		if (n->key > p->key) {
			p->rightChild = n->leftChild;
		} else {
			p->leftChild = n->leftChild;
		}
	}
}

searchtree makesearchtree(int *array, int size)
{
	int i;
	searchtree s = (searchtree)malloc(sizeof(pNode));
	(*s) = NULL;

	for (i = 0; i < size; i++) {
		pNode n = (pNode)malloc(sizeof(node));
		initializenode1(n, array[i]);
		insert(n, s);
	}

	return s;
}

void printfSearchTree(searchtree s)
{
	if (s == NULL || (*s) == NULL)
		return;

	printfNode(*s);

}

void printfNode(pNode n)
{
	int leftChild = -1, rightChild = -1;
	if (n == NULL)
		return;
	if (n->leftChild != NULL) {
		leftChild = n->leftChild->key;
	}

	if (n->rightChild != NULL) {
		rightChild = n->rightChild->key;
	}

	printf("%d (%d, %d)\n", n->key, leftChild, rightChild);
	printfNode(n->leftChild);
	printfNode(n->rightChild);

}

searchtree join(searchtree s1, pNode n, searchtree s2)
{
	searchtree t = (searchtree)malloc(sizeof(pNode));
	n->leftChild = *s1;
	n->rightChild = *s2;

	*t = n;
	return t;
}

void split(pNode i, searchtree s, searchtree s1, searchtree s2)
{


}

